#include <stdio.h>
#include <stdlib.h>
#include <time.h>


#define MAXSIZE 20

/**
 * 数组初始化（生成随机数）
 * @param A
 * @param length
 */
void ArrayInit(int A[], int length) {
    srand(time(NULL));  // 初始化随机种子
    for (int i = 0; i < length; ++i) {
        A[i] = rand() % 100;
    }
}

/**
 * 打印数组
 * @param A
 * @param length
 */
void ArrayPrint(int A[], int length) {
    for (int i = 0; i < length && i < MAXSIZE; ++i) {
        printf("%3d ", A[i]);
    }
    printf("\n");
}

/**
 * 用第一个元素将序列分成左右两个部分
 * （每次确定第一个元素在范围内的位置）
 * @param A
 * @param low
 * @param high
 * @return
 */
int Partition(int A[], int low, int high) {
    int pivot = A[low];     // 用第一个元素作为枢轴（暂存）
    while (low < high) {
        // 取第一个元素作为枢轴，所以划分右侧
        while (low < high && A[high] > pivot) {
            --high;
        }
        A[low] = A[high];   // 比枢轴小的元素放左边
        while (low < high && A[low] < pivot) {
            ++low;
        }
        A[high] = A[low];   // 比枢轴大的元素放右边
    }
    A[low] = pivot;         // 最终low = high时跳出循环，low/high为枢轴的最终位置
    return low;
}

/**
 * 快速排序
 * @param A
 * @param length
 */
void QuickSort(int A[], int low, int high) {
    if (low < high) {
        int pivotPos = Partition(A, low, high);
        QuickSort(A, low, pivotPos-1);
        QuickSort(A, pivotPos+1, high);
    }
}


int main() {
    printf("Hello, QuickSort!\n");

    int A[MAXSIZE];         // 定义数组
    int length = 10;        // 设置使用的长度

    // 初始化数组生成随机数
    ArrayInit(A, length);
    ArrayPrint(A, length);

    // 插入排序
    QuickSort(A, 0, length-1);
    ArrayPrint(A, length);

}